package ACWing.mathematicalknowledge.欧拉函数;
//873. 欧拉函数

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2023/1/11 15:48
 */
public class EulerFunction {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while (n-->0){
            int x=sc.nextInt();
            int res=x;
            for (int i = 2; i <=x/i ; i++) {
                if(x%i==0){
                    res=res/i*(i-1);
                    while (x%i==0){
                        x=x/i;

                    }
                }
            }
            if(x>1){
                res=res/x*(x-1);
            }
            System.out.println(res);
        }
    }
}
